package hash;

public class HashTableDemo {
    public static void main(String[] args) {
        EmpHashTable eht = new EmpHashTable(6);
        eht.add(new Emp(8, "xdq"));
        eht.add(new Emp(19, "lc"));
        eht.list();
        eht.search(8);
        eht.search(7);
    }
}

class Emp {
    int id;
    String name;
    Emp next;
    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

class EmpLinkedList {
    private Emp head;
    private Emp rear; // 尾指针指向最后一个节点
    public void add(Emp emp) {
        if (head == null) {
            head = emp;
            rear = head;
            return;
        }
        rear.next = emp;
        rear = emp;
    }

    public void list(int no) {
        if (!isEmpty()) {
            Emp currentEmp = head;
            while (currentEmp != null) {
                System.out.printf("=> id=%d, name=%s \t", currentEmp.id, currentEmp.name);
                currentEmp = currentEmp.next;
            }
            System.out.println();
        } else {
            System.out.println("此链表为空");
        }
    }

    public boolean isEmpty() {
        return head == null;
    }

    // 查找成功返回 True，失败返回 False
    public boolean search(int id) {
        Emp curEmp = head;
        while (curEmp != null) {
            if (curEmp.id == id) {
                System.out.print("查找成功，姓名为：" + curEmp.name + ", ");
                return true;
            }
            curEmp = curEmp.next;
        }
        System.out.println("查找失败，表中无该节点。");
        return false;
    }
}

class EmpHashTable {
    private EmpLinkedList[] lists;
    private int size;
    public EmpHashTable(int size) {
        this.size = size;
        lists = new EmpLinkedList[size];
        for (int i = 0; i < size; i++) {
            lists[i] = new EmpLinkedList();
        }
    }

    public void add(Emp emp) {
        lists[hashFunc(emp.id)].add(emp);
    }

    public void list() {
        for (int i = 0; i < size; i++) {
            System.out.printf("第 %d 号链表信息：", i);
            lists[i].list(i);
        }
    }

    private int hashFunc(int id) {
        return id % size;
    }

    public void search(int id) {
        int index = hashFunc(id); // hash 值
        if(lists[index].search(id)) {
            System.out.printf("在 %d 号链表中找到\n", index);
        }
    }
}
